Validate binary search tree [Morris Traversal]

Time: O(N); Space: O(1); medium

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows: * The left subtree of a node contains only nodes with keys less than the node’s key. * The right subtree of a node contains only nodes with keys greater than the node’s key. * Both the left and right subtrees must also be binary search trees.

Example 1:

  2
 / \
1   3

Input: root = {TreeNode} [2,1,3]

Output: True

Example 2:

  5
 / \
1   4
   / \
  3   6

Input: root = {TreeNode} [5,1,4,null,null,3,6]

Output: False

Explanation:

  • The root node’s value is 5 but its right child’s value is 4.

1. Morris Traversal Solution

[1]:

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

[2]:

class Solution1(object):
    """
    Time: O(N)
    Space: O(1)
    """
    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: boolean
        """
        prev, cur = None, root
        while cur:
            if cur.left is None:
                if prev and prev.val >= cur.val:
                    return False
                prev = cur
                cur = cur.right
            else:
                node = cur.left
                while node.right and node.right != cur:
                    node = node.right

                if node.right is None:
                    node.right = cur
                    cur = cur.left
                else:
                    if prev and prev.val >= cur.val:
                        return False
                    node.right = None
                    prev = cur
                    cur = cur.right

        return True

[3]:

s = Solution1()

root = TreeNode(2)
root.left = TreeNode(1)
root.right = TreeNode(3)
assert s.isValidBST(root) == True

root = TreeNode(5)
root.left = TreeNode(1)
root.right = TreeNode(4)
root.left.left = None
root.left.right = None
root.right.left = TreeNode(3)
root.right.right = TreeNode(6)
assert s.isValidBST(root) == False

2. Recursion

[4]:

class Solution2(object):
    def isValidBST(self, root):
        return self.isValidBSTRecu(root, float('-inf'), float('inf'))

    def isValidBSTRecu(self, root, low, high):
        if root is None:
            return True

        return low < root.val and root.val < high \
               and self.isValidBSTRecu(root.left, low, root.val) \
               and self.isValidBSTRecu(root.right, root.val, high)

[5]:

s = Solution2()

root = TreeNode(2)
root.left = TreeNode(1)
root.right = TreeNode(3)
assert s.isValidBST(root) == True

root = TreeNode(5)
root.left = TreeNode(1)
root.right = TreeNode(4)
root.left.left = None
root.left.right = None
root.right.left = TreeNode(3)
root.right.right = TreeNode(6)
assert s.isValidBST(root) == False